The invention relates to identification of predefined patterns in digital data. More particularly, the invention relates to a scheme for identifying a string of data using a multi-stage searching technique.
In recent years computer networks have changed many aspects of life. For example, in a few short years, the Internet has changed the manner in which information is sent and received, the way goods and services are bought and sold, and the way that financial matters are handled. Standard applications such as web browsers and protocols such as Transmission Control Protocol/Internet Protocol (TCP/IP) have become integral to the success of networks.
In order to provide more information and services to more people and to more places, networks have become easier to use and more reliable. However, making the network operate smoothly requires a high degree of interoperability, scalability and platform independence. One aspect of networking is policy enforcement. Policy enforcement provides a way to give some types of traffic, such as real-time video, priority over other, less important traffic, such as electronic mail. Policy enforcement can also provide intrusion detection.
Policy enforcement has been provided with general purpose computers, fixed function appliances, and/or switches and routers. General purpose computers that provide policy enforcement typically include two or more network interface cards (NICs) that provide multiple connections to the network. Policy enforcement is provided by the processor of the general purpose computer. However, general purpose computers are not developed to perform high-speed operations on network packets. Because of this policy enforcement with general purpose computers is a bottleneck to network performance.
In an attempt to overcome the performance limitations of using general purpose computers for policy enforcement, fixed-function devices specifically designed to support policy enforcement have been developed. Typically, these fixed-function appliances have a processor and/or customized hardware and two or more NICs. While fixed-function appliances can be fast enough for some network operations, scalability is restricted.
Switches and routers have been used to provide policy enforcement. However, switches and routers typically do not have sufficient processing power to provide policy enforcement in addition to switching and routing functionality. The processors of the switches and routers must be used for both policy enforcement and for switching and/or routing functionality, which decreases network performance. Alternatively, switches and routers can be designed with more powerful processors, which increases the cost of the switches and routers.
A method and apparatus for searching for a string of data matching a predetermined string of data is described. A first stage search is performed on the data. The first stage search identifies one or more potential strings of interest having a pattern matching a portion of the predetermined string. A second stage search is performed on the data corresponding to the one or more potential strings of interest to determine whether a match exists. In one embodiment the first stage search is performed by a first processor and the second stage search is performed by a second processor. In another embodiment, the first stage search and the second stage search are performed by a single processor if performed in sequence.